In some navigation systems, the current position of a vehicle can be accurately estimated by updating a previous position of the vehicle, which is detected using radio signals from global positioning system (GPS) satellites, based on the travel distance and the direction of the vehicle obtained by a speed sensor and a gyro sensor.
However, in a situation where radio signals from GPS satellites cannot be received, the position estimated by autonomous navigation deviates from the actual position and the accuracy of the estimated position decreases gradually as time passes. To cope with this problem, various methods for correcting a vehicle position estimated by autonomous navigation have been proposed.
For example, in a map matching method, a position estimated by autonomous navigation is corrected by using map data of a navigation system. According to a map matching method, positions of a vehicle estimated by autonomous navigation are mapped onto positions in map data, which are represented by nodes (e.g. intersections) and links (e.g. roads) connecting the nodes, so that the estimated traveling path of the vehicle matches actual roads.
However, generally, map data are not accurate enough to obtain satisfactory results by a map matching method. A method disclosed in patent document 1 tries to solve this problem. In the disclosed method, the position and direction of a vehicle estimated by autonomous navigation are corrected by selecting from map data a road having a position and a direction closest to the estimated position and direction and by mapping the estimated position and direction onto those of the selected road.    [Patent document 1] Japanese Patent Application Publication No. 2002-213979